package com.algorithm5;

import java.util.Arrays;

public class InsertionSort {


    public static void sort(int[] array){
        //插入排序:分为已排序区和未排序区，每次都从未排序区拿一个插入已排序区的对应位置
        for(int i=0;i<array.length-1;i++){
            int j = i+1;
            int temp = array[j];
            while(j>0 && array[j-1]>temp){
                //移位
                array[j] = array[j-1];
                j--;
            }
            array[j] = temp;
            System.out.println("i="+i+"-->"+ Arrays.toString(array));
        }
    }


    public static void main(String[] args){
        int[] array = new int[]{4,3,6,8,9,7,10,5,1,2};
        System.out.println("array:"+ Arrays.toString(array));
        sort(array);
        System.out.println("sorted array:"+ Arrays.toString(array));

    }
}
